package 左哥算法.ch11字符串相关;

import org.junit.Test;

public class Ch02Manachar算法 {

    @Test
    public void test(){

        System.out.println(longestPalindrome("112212"));
    }
    /**
     * manachar算法用于查找最长回文字串
     */
    public String longestPalindrome(String s) {
        char[] chars = addPartition(s);
        int[] radius=new int[chars.length];
        int c=-1,r=-1,l=-1,maxIndex=0;
        for (int i = 0; i < chars.length; i++) {
            if (i>r){   //i在r的右侧
                radius[i] = getRadius(chars, i - 1, i + 1); //暴力解
                r=i+radius[i];
                l=i-radius[i];
                c=i;
                maxIndex=radius[i]>radius[maxIndex]?i:maxIndex;
            }else{
                int j=c-(i-c);      //对称点
                if ((j-radius[j])>l){  //当前位置对称点(j)的回文边界（j-radius[j]）在L的右侧，（彻底在LR里面）
                    radius[i]=radius[j];
                }else if ((j-radius[j])<l){  //当前位置对称点(j)的回文边界（j-radius[j]）在L的左侧，部分在LR的外面
                    radius[i]=r-i;
                }else {     //对称点的回文区域边界与L相同
                    radius[i]= getRadius(chars, i - (r - i) - 1, r + 1);    //r的右侧，以及r关于i对称点的右侧
                    if (radius[i]>radius[j]) {
                        r=i+radius[i];
                        l=i-radius[i];
                        c=i;
                        maxIndex=radius[i]>radius[maxIndex]?i:maxIndex;
                    }
                }
            }
        }
        l=(maxIndex-radius[maxIndex])/2;    //最长回文串的左侧
        r=(maxIndex+radius[maxIndex])/2;    //最长回文串的右侧
        return s.substring(l,r);
    }

    /**
     * 给字符串中每个字符添加分割字符。（分割字符不影响结果）
     * @param s
     * @return
     */
    public char[] addPartition(String s){
        char[] chars=new char[s.length()*2+1];
        for (int i = 0; i < chars.length; i++) {
            chars[i]=i%2==0?'#':s.charAt(i/2);
        }
        return chars;
    }
    /**
     * 获取回文串的半径（暴力解）
     */
    public int getRadius(char[] chars,int l,int r){
        while (l>=0&&r<chars.length&&chars[l]==chars[r]){
            l--;
            r++;
        }
        return (r-l)/2-1;   //-1是做r--和i++
    }
}
